package com.sheng.leetcode.year2022.month07.day01;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/07/01
 *
 * 241. 为运算表达式设计优先级
 *
 * 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
 * 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
 *
 * 示例 1：
 * 输入：expression = "2-1-1"
 * 输出：[0,2]
 * 解释：
 * ((2-1)-1) = 0
 * (2-(1-1)) = 2
 *
 * 示例 2：
 * 输入：expression = "2*3-4*5"
 * 输出：[-34,-14,-10,-10,10]
 * 解释：
 * (2*(3-(4*5))) = -34
 * ((2*3)-(4*5)) = -14
 * ((2*(3-4))*5) = -10
 * (2*((3-4)*5)) = -10
 * (((2*3)-4)*5) = 10
 *
 * 提示：
 * 1 <= expression.length <= 20
 * expression 由数字和算符 '+'、'-' 和 '*' 组成。
 * 输入表达式中的所有整数值在范围 [0, 99] 
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/different-ways-to-add-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0241 {

    @Test
    public void test01(){
        String expression = "2-1-1";
//        String expression = "2*3-4*5";
        System.out.println(new Solution().diffWaysToCompute(expression));
    }

}
//class Solution {
//    public List<Integer> diffWaysToCompute(String expression) {
//        return null;
//    }
//}

//class Solution {
//    static final int ADDITION = -1;
//    static final int SUBTRACTION = -2;
//    static final int MULTIPLICATION = -3;
//
//    public List<Integer> diffWaysToCompute(String expression) {
//        List<Integer> ops = new ArrayList<Integer>();
//        for (int i = 0; i < expression.length();) {
//            if (!Character.isDigit(expression.charAt(i))) {
//                if (expression.charAt(i) == '+') {
//                    ops.add(ADDITION);
//                } else if (expression.charAt(i) == '-') {
//                    ops.add(SUBTRACTION);
//                } else {
//                    ops.add(MULTIPLICATION);
//                }
//                i++;
//            } else {
//                int t = 0;
//                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
//                    t = t * 10 + expression.charAt(i) - '0';
//                    i++;
//                }
//                ops.add(t);
//            }
//        }
//        List<Integer>[][] dp = new List[ops.size()][ops.size()];
//        for (int i = 0; i < ops.size(); i++) {
//            for (int j = 0; j < ops.size(); j++) {
//                dp[i][j] = new ArrayList<Integer>();
//            }
//        }
//        return dfs(dp, 0, ops.size() - 1, ops);
//    }
//
//    public List<Integer> dfs(List<Integer>[][] dp, int l, int r, List<Integer> ops) {
//        if (dp[l][r].isEmpty()) {
//            if (l == r) {
//                dp[l][r].add(ops.get(l));
//            } else {
//                for (int i = l; i < r; i += 2) {
//                    List<Integer> left = dfs(dp, l, i, ops);
//                    List<Integer> right = dfs(dp, i + 2, r, ops);
//                    for (int lv : left) {
//                        for (int rv : right) {
//                            if (ops.get(i + 1) == ADDITION) {
//                                dp[l][r].add(lv + rv);
//                            } else if (ops.get(i + 1) == SUBTRACTION) {
//                                dp[l][r].add(lv - rv);
//                            } else {
//                                dp[l][r].add(lv * rv);
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        return dp[l][r];
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/different-ways-to-add-parentheses/solution/wei-yun-suan-biao-da-shi-she-ji-you-xian-lyw6/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    char[] cs;
    public List<Integer> diffWaysToCompute(String s) {
        //cs作为运算表达式的字符数组
        cs = s.toCharArray();
        return dfs(0, cs.length - 1);
    }

    /**
     *
     * @param l：l代表左边界
     * @param r：r代表右边界
     * @return
     */
    List<Integer> dfs(int l, int r) {
        //ans存储所有可能的结果
        List<Integer> ans = new ArrayList<>();
        for (int i = l; i <= r; i++) {
            //如果当前字符为数字，代表没有遇到运算符，继续循环直到遇见运算符为止
            if (cs[i] >= '0' && cs[i] <= '9') {
                continue;
            }
            //走到这一步意味着，当前i所在的位置是运算符
            //l1：运算符左边的表达式的结果集，l2：运算符右边的表达式的结果集
            List<Integer> l1 = dfs(l, i - 1), l2 = dfs(i + 1, r);
            //循环表达式左边的结果集
            for (int a : l1) {
                //循环表达式右边的结果集
                for (int b : l2) {
                    //cur作为左右两边表达式计算出来的结果
                    int cur = 0;
                    //判断当前i位置的运算符是哪一种
                    if (cs[i] == '+') {
                        cur = a + b;
                    } else if (cs[i] == '-') {
                        cur = a - b;
                    } else {
                        cur = a * b;
                    }
                    //将结果集添加到ans中
                    ans.add(cur);
                }
            }
        }
        //如果ans为空，代表当前表达式为纯数字，没有结果集，那么就将当前表达式转换为数字，存放到ans中
        if (ans.isEmpty()) {
            //cur代表当前数值
            int cur = 0;
            //从第一个字符开始，循环到最后一个字符，每次 * 10
            for (int i = l; i <= r; i++) {
                cur = cur * 10 + (cs[i] - '0');
            }
            ans.add(cur);
        }
        return ans;
    }
}
//
//为了方便，我们令 expression 为 s。
//数据范围为 20，且要统计所有的计算结果，我们可以运用 DFS 爆搜所有方案。
//给定的 s 只有数字和运算符，我们可以根据运算符将式子分为左右两部分，
//设计递归函数 List<Integer> dfs(int l, int r)，含义为搜索子串 s[l...r] 的所有运算结果。
//最终答案为 dfs(0,n-1)，其中 n 为入参字符串的长度，
//同时我们有显而易见的递归出口：当给定的 s[l...r] 不包含任何运算符时，搜索结果为 s[l...r] 所代表的数字本身。
//考虑如何对任意 s[l...r] 进行计算：我们可以通过枚举 s[l...r] 范围内的所有的运算符位置来进行爆搜，
//假设当前枚举到的 s[i] 为运算符，我们可以递归运算符的左边 dfs(l,i-1) 拿到左边所有的结果，
//递归运算符右边 dfs(i+1,r) 拿到右边的所有结果，结合「乘法原理」即可知道以当前运算符 s[i] 为分割点的表达式的所有方案。
//不难发现，上述过程都是由「小表达式」的结果推导出「大表达式」的结果，因此也可以运用「区间 DP」方式进行求解，复杂度与 DFS 一致。
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/different-ways-to-add-parentheses/solution/by-ac_oier-z07i/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
